package com.lw.leetcode.back.b;

/**
 * Created with IntelliJ IDEA.
 * back
 * 1559. 二维网格图中探测环
 *
 * @author liw
 * @version 1.0
 * @date 2021/12/17 13:23
 */
public class ContainsCycle {

    private char[][] grid;
    private int a;
    private int b;

    public boolean containsCycle(char[][] grid) {
        this.a = grid.length;
        this.b = grid[0].length;
        this.grid = grid;
        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                char t = grid[i][j];
                if (t < 'a') {
                    continue;
                }
                grid[i][j] = (char) (t & 0XFFFFFFDF);
                if (find(i - 1, j, 0, t)) {
                    return true;
                }
                if (find(i + 1, j, 1, t)) {
                    return true;
                }
                if (find(i, j + 1, 3, t)) {
                    return true;
                }
                if (find(i, j - 1, 2, t)) {
                    return true;
                }
            }
        }
        return false;
    }

    private boolean find(int x, int y, int flag, char t) {
        if (x < 0 || x == a || y < 0 || y == b) {
            return false;
        }
        if (grid[x][y] != t) {
            return grid[x][y] == (t & 0XFFFFFFDF);
        }
        grid[x][y] = (char) (t & 0XFFFFFFDF);
        if (flag != 1) {
            if (find(x - 1, y, 0, t)) {
                return true;
            }
        }
        if (flag != 0) {
            if (find(x + 1, y, 1, t)) {
                return true;
            }
        }
        if (flag != 2) {
            if (find(x, y + 1, 3, t)) {
                return true;
            }
        }
        if (flag != 3) {
            return find(x, y - 1, 2, t);
        }
        return false;
    }

}
